package com.ss.travelsal;

/**
 * @author 叁昇
 * @create 2021-02-28-10:12
 */
public class MorrisTravelsal {
    public static class Node {
        public int value;
        Node left;
        Node right;
        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * Morris 遍历一般方法：
     *  开始当前节点 cur 来到整树头
     *   1）cur 无左树，cur = cur.right
     *   2）cur 有左树，找到左树的最右节点 mostRight
     *    ① mostRight 的右指针指向 null 时：
     *     mostRight.right = cur，
     *     cur = cur.left
     *    ② mostRight 的右指针指向 cur 时：
     *     mostRight.right = null,
     *     cur = cur.right
     * 可见，有左树的节点必经过两次
     * 空间复杂度极少为 O(1)，用空闲指针；遍历了最多两倍节点数，时间复杂度为 O(N)
     * @param head
     */
    public static void morris(Node head){
        if (head == null){
            return;
        }
        Node cur = head; // current 目前所在节点
        Node mostRight = null; // 左树最右节点
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 有左树时
                while (mostRight.right != null && mostRight.right != cur) { // 找到 cur 左树上真实的最右节点
                    mostRight = mostRight.right;
                } // 第一次来到当前节点或者第二次来到当前节点跳出循环，mostRight 一定是 cur 左树上的最右节点
                if (mostRight.right == null) { // 第一次来到 cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            cur = cur.right;
        }
    }

    /**
     * Morris 中序遍历
     * 节点即将往右移动时才打印
     * @param head
     */
    public static void morrisIn(Node head){
        if (head == null){
            return;
        }
        Node cur = head; // current 目前所在节点
        Node mostRight = null; // 左树最右节点
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 有左树时
                while (mostRight.right != null && mostRight.right != cur) { // 找到 cur 左树上真实的最右节点
                    mostRight = mostRight.right;
                } // 第一次来到当前节点或者第二次来到当前节点跳出循环，mostRight 一定是 cur 左树上的最右节点
                if (mostRight.right == null) { // 第一次来到 cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
    }

    /**
     * Morris 先序遍历
     * 能到达自己两次的节点第一次打印，只能到达自己一次的节点直接打印
     * @param head
     */
    public static void morrisPre(Node head){
        if (head == null){
            return;
        }
        Node cur = head; // current 目前所在节点
        Node mostRight = null; // 左树最右节点
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 有左树时
                while (mostRight.right != null && mostRight.right != cur) { // 找到 cur 左树上真实的最右节点
                    mostRight = mostRight.right;
                } // 第一次来到当前节点或者第二次来到当前节点跳出循环，mostRight 一定是 cur 左树上的最右节点
                if (mostRight.right == null) { // 第一次来到 cur
                    mostRight.right = cur;
                    System.out.println(cur.value + " ");
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            } else {
                System.out.println(cur.value + " ");
            }
            cur = cur.right;
        }
    }

    /**
     * Morris 后序遍历
     * 能到达自己两次的节点且第二次回到自己时才进行逆序打印（打印其左树右边界），完成后打印整棵树的右边界
     * @param head
     */
    public static void morrisPos(Node head){
        if (head == null){
            return;
        }
        Node cur = head; // current 目前所在节点
        Node mostRight = null; // 左树最右节点
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 有左树时
                while (mostRight.right != null && mostRight.right != cur) { // 找到 cur 左树上真实的最右节点
                    mostRight = mostRight.right;
                } // 第一次来到当前节点或者第二次来到当前节点跳出循环，mostRight 一定是 cur 左树上的最右节点
                if (mostRight.right == null) { // 第一次来到 cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                    printRightEdge(cur.left);
                }
            }
            cur = cur.right;
        }
        printRightEdge(head);
        System.out.println();
    }

    /**
     * 打印右边界
     * @param head
     */
    public static void printRightEdge(Node head) {
        Node tail = reverseRightEdge(head);
        Node cur = tail;
        while (cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.right;
        }
        reverseRightEdge(tail);
    }

    /**
     * 反转右边界
     * @param from
     * @return
     */
    public static Node reverseRightEdge(Node from) {
        Node pre = null;
        Node next = null;
        while (from != null) {
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }

    /**
     * 判断是否为搜索二叉树
     * @param head
     * @return
     */
    public static boolean isBST(Node head){
        if (head == null){
            return true;
        }
        Node cur = head; // current 目前所在节点
        Node mostRight = null; // 左树最右节点

        Integer pre = null;

        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 有左树时
                while (mostRight.right != null && mostRight.right != cur) { // 找到 cur 左树上真实的最右节点
                    mostRight = mostRight.right;
                } // 第一次来到当前节点或者第二次来到当前节点跳出循环，mostRight 一定是 cur 左树上的最右节点
                if (mostRight.right == null) { // 第一次来到 cur
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            if (pre != null && pre >= cur.value) return false;
            pre = cur.value;
            cur = cur.right;
        }
        return true;
    }

    /**
     * 计算最小叶节点高度
     * @param head
     * @return
     */
    public static int minHeight(Node head){
        if (head == null){
            return 0;
        }
        Node cur = head; // current 目前所在节点
        Node mostRight = null; // 左树最右节点

        int curLevel = 0;
        int minHeight = Integer.MAX_VALUE;

        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) { // 有左树时
                int rightEdgeSize = 1;
                while (mostRight.right != null && mostRight.right != cur) { // 找到 cur 左树上真实的最右节点
                    rightEdgeSize++;
                    mostRight = mostRight.right;
                } // 第一次来到当前节点或者第二次来到当前节点跳出循环，mostRight 一定是 cur 左树上的最右节点
                if (mostRight.right == null) { // 第一次来到 cur
                    curLevel++;
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else { // 第二次到达
                    if (mostRight.left == null) {
                        minHeight = Math.min(minHeight, curLevel);
                    }
                    curLevel -= rightEdgeSize;
                    mostRight.right = null;
                }
            } else { // 只有一次到达
                curLevel++;
            }
            cur = cur.right;
        }
        int finalRight = 1;
        cur = head;
        while (cur.right != null) {
            finalRight++;
            cur = cur.right;
        }
        if (cur.left == null && cur.right == null) {
            minHeight = Math.min(minHeight, finalRight);
        }
        return minHeight;
    }
}
